/**
 * 85. 最大矩形
 * https://leetcode-cn.com/problems/maximal-rectangle/
 */

let stack;
let top;
let lowersLeft;
let lowersRight;

/**
 * @param {number[]} heights
 * @return {number}
 */
function maxArea(heights) {
  top = -1;
  for (let i = 0; i < heights.length; i += 1) {
    while (top >= 0 && heights[stack[top]] >= heights[i]) {
      top -= 1;
    }
    lowersLeft[i] = top >= 0 ? stack[top] : -1;
    top += 1;
    stack[top] = i;
  }
  top = -1;
  for (let i = heights.length - 1; i >= 0; i -= 1) {
    while (top >= 0 && heights[stack[top]] >= heights[i]) {
      top -= 1;
    }
    lowersRight[i] = top >= 0 ? stack[top] : heights.length;
    top += 1;
    stack[top] = i;
  }
  let max = 0;
  for (let i = 0; i < heights.length; i += 1) {
    const area = heights[i] * (lowersRight[i] - lowersLeft[i] - 1);
    if (area > max) {
      max = area;
    }
  }
  return max;
}

/**
 * @param {string[][]} matrix
 * @return {number}
 */
function maximalRectangle(matrix) {
  if (!matrix.length) {
    return 0;
  }
  stack = new Array(matrix[0].length).fill(0);
  lowersLeft = new Array(matrix[0].length).fill(0);
  lowersRight = new Array(matrix[0].length).fill(0);
  const heights = new Array(matrix[0].length).fill(0);
  let max = 0;
  for (let i = 0; i < matrix.length; i += 1) {
    const row = matrix[i];
    for (let j = 0; j < row.length; j += 1) {
      if (row[j] === '1') {
        heights[j] += 1;
      } else {
        heights[j] = 0;
      }
    }
    max = Math.max(max, maxArea(heights));
  }
  return max;
}

console.log(maximalRectangle([
  ['1', '0', '1', '0', '0'],
  ['1', '0', '1', '1', '1'],
  ['1', '1', '1', '1', '1'],
  ['1', '0', '0', '1', '0'],
]) === 6);
console.log(maximalRectangle([]) === 0);
console.log(maximalRectangle([['0']]) === 0);
console.log(maximalRectangle([['1']]) === 1);
console.log(maximalRectangle([['0', '0']]) === 0);
